1. Technical Field of the Invention
The present invention relates in general to a relational processor. More specifically, the present invention relates to an improved relational processor that is used to implement scalable high speed database systems and particularly to relational database systems
2. Description of the Related Art
There are various systems for storing, searching and accessing data in relational databases. High speed database requirements are characterized in terms of memory capacity, processing speed, types of operations to be performed and by the characteristics of the data. However, current databases are too slow to make it practical to routinely solve complex logic problems. Real-time relational databases are not extant.
U.S. Pat. No. 6,334,123 issued to Ross on Dec. 25, 2001 discloses a method of relational processing where a query of one or more databases of records returns the query result in the form of one or more threads of parallel words. A collection generator generates one or more intermediate vectors of serial bit streams from the one or more threads, and processes the one or more intermediate vectors with a relational processor. The relational processor is operable to perform one or more logical operations thereon in a single pass, and outputs a contiguous serial bit stream. But such a relational processor is not efficient to solve complex logic problems.
U.S. Patent Application. No. 20050262294 issued to Nabil Bitar, on May 5, 2004 discloses a TCAM-Memory hybrid scheme that enables high search rates with memory based search and the TCAM can be configured to return a memory pointer to a head of an action list. In such a hybrid scheme the actions are daisy-chained in a strict order in memory and are applied to the packet in the same order. However, the attempts to improve memory storage capacity by the daisy chained TCAM components leads in a slow down processing.
U.S. Pat. No. 6,738,862 issued to Rose, on May 18, 2004 provides a method and system for flexible matching of data in a CAM. The entries of the CAM are logically grouped in a set of blocks, each block having a single mask that applies to all entries in the block. However, the CAM has a hard limit on memory capacity. Furthermore, the power consumption of the CAM is too large for large systems.
One prior art, taught in U.S. Pat. No. 6,237,061 issued to Srinivasan on May 22, 2001 provides a ternary content addressable memory to perform a longest prefix match search. Each content addressable memory cell within the ternary content addressable memory has an associated mask cell so that the content addressable memory cells may be individually masked. Since each CAM entry is masked according to an associated prefix value, the ternary CAM requires only one search operation to locate the CAM entry having the longest matching prefix. However, such a longest prefix match search process is very difficult to implement.
Hence, it can be seen, that there is a need for an ultra high speed relational processor that would be scalable both in speed and memory capacity. Further, such a device would be capable of solving complex logic problems in real time. Such a needed device does rely on preordering of database keys and can be updated dynamically without presorting. Such a device would also permit a plurality of relations to be dynamically maintained without switchover overhead. Such a needed device is easy to reprogram for changes in input relations in contrast to hash devices in which the algorithms are tailored to the input. Such a needed device introduces a longest prefix match search that is easy to implement and efficient. The device would be capable of performing operations between relational domains and between relations and be user programmable. Moreover, such a device would have lower power consumption and is more economical. The present invention accomplishes these objectives.